무차별 대입 검색
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
무차별 대입 검색은 가능한 모든 해 후보를 체계적으로 검사하여 문제를 해결하는 알고리즘으로, 'first', 'next', 'valid', 'output'의 네 가지 프로시저를 구현하여 작동한다. 이 방식은 구현이 간단하지만, 후보 해의 수가 많은 문제에서는 '조합 폭발'로 인해 비효율적이다. 탐색 공간을 줄이거나 탐색 순서를 최적화하는 기법, 문제에 대한 사전 지식(휴리스틱) 활용 등을 통해 검색 속도를 향상시킬 수 있다. 다른 검색 알고리즘, 특히 제약 조건을 활용하거나 탐색 공간을 줄이는 알고리즘과의 비교를 통해 무차별 대입 검색의 한계와 개선 방안을 알 수 있다.
무차별 대입 탐색은 일반적으로 다음 네 가지 절차를 통해 구현된다.
무차별 대입 방식의 주요 단점은 많은 실제 문제에서 가능한 경우의 수가 지나치게 많다는 것이다. 예를 들어, 어떤 숫자의 약수를 찾을 때, 테스트해야 할 경우의 수는 주어진 숫자 ''n''에 따라 결정된다. 만약 ''n''이 16자리 십진수라면, 검색에는 최소 1015개의 컴퓨터 명령이 필요하며, 이는 일반적인 PC에서 며칠이 걸리는 작업이다. ''n''이 19자리 십진수를 갖는 무작위 64비트 자연수라면, 검색에 약 10년이 걸릴 것이다.
2. 기본 알고리즘
프로시저 설명 first(P) P의 첫 번째 해 후보를 생성한다. next(P, c) 현재 해 후보 c 다음에 오는 P의 다음 해 후보를 생성한다. valid(P, c) 해 후보 c가 P의 해인지 확인한다. output(P, c) P의 해 c를 적절하게 표시하거나 다른 애플리케이션에 전달한다.
`next` 프로시저는 ''P''의 해 후보가 더 이상 없을 때 실제 후보와 구별되는 관례적인 데이터 값인 Λ(람다)를 반환한다. 마찬가지로 `first`도 ''P''의 해 후보가 전혀 없을 경우 Λ를 반환한다.
2. 1. 절차
무차별 대입 검색을 적용하기 위해서는 해결하고자 하는 문제의 특정 인스턴스 데이터 ''P''를 인수로 받아들이는 네 가지 프로시저 ''first'', ''next'', ''valid'', ''output''을 구현해야 한다.
# ''first''(''P''): 문제 ''P''에 대한 첫 번째 해 후보를 생성한다.
# ''next''(''P'', ''c''): 현재 해 후보 ''c'' 다음에 오는, 문제 ''P''에 대한 다음 해 후보를 생성한다.
# ''valid''(''P'', ''c''): 해 후보 ''c''가 문제 ''P''의 실제 해인지 확인한다.
# ''output''(''P'', ''c''): 문제 ''P''의 해 ''c''를 출력하거나, 필요에 따라 다른 형태로 활용한다.
''next'' 프로시저는 ''P''에 대한 해 후보가 더 이상 없을 때를 알려야 한다. 이를 위해, 실제 해 후보와는 구별되는 특별한 값 Λ(람다)를 사용한다. ''first'' 프로시저 역시 ''P''에 대한 해 후보가 전혀 없을 경우 Λ를 반환한다.
무차별 대입 검색 알고리즘은 다음과 같이 표현할 수 있다.
''c'' ← ''first''(''P'')
'''while''' ''c'' ≠ Λ '''do'''
'''if''' ''valid''(''P'', ''c'') '''then'''
''output''(''P'', ''c'')
''c'' ← ''next''(''P'', ''c'')
'''end while'''
예를 들어, 정수 ''n''의 약수를 찾는 문제를 생각해 보자. 이 경우,
Λ를 ''n'' + 1로 정의하면, ''n'' ≥ 1 및 ''c'' < ''n'' 조건 검사는 생략 가능하다.
이 알고리즘은 주어진 문제 ''P''의 모든 해를 찾을 때까지 반복한다. 필요에 따라, 첫 번째 해를 찾거나, 일정 개수의 해를 찾거나, 특정 조건을 만족할 때까지만 알고리즘을 실행하도록 수정할 수 있다.
2. 2. 알고리즘 표현
무차별 대입 탐색 알고리즘은 다음 절차를 따른다. 여기서 Λ(람다)는 더 이상 유효한 후보해가 없음을 나타내는 특수한 값이다.[1]
''c'' ← ''first''(''P'')
'''while''' ''c'' ≠ Λ '''do'''
'''if''' ''valid''(''P'',''c'') '''then'''
''output''(''P'', ''c'')
''c'' ← ''next''(''P'', ''c'')
'''end while'''
예를 들어, 정수 ''n''의 약수를 찾을 때, 문제 인스턴스 데이터 ''P''는 해당 정수 ''n''이다. ''first''(''n'')을 호출하면 ''n'' ≥ 1일 때 정수 1을 반환하고, 그렇지 않으면 Λ를 반환한다. ''next''(''n'',''c'')를 호출하면 ''c'' < ''n''이면 ''c'' + 1을 반환하고, 그렇지 않으면 Λ를 반환한다. ''valid''(''n'',''c'')는 ''c''가 ''n''의 약수이면 '''true'''를 반환한다. Λ를 ''n'' + 1로 설정하면 ''n'' ≥ 1 및 ''c'' < ''n'' 조건 검사를 생략할 수 있어 구현이 간단해진다.[1]
3. 조합 폭발
데이터 크기가 증가함에 따라 경우의 수가 급격하게 증가하는 현상은 모든 종류의 문제에서 발생한다. 예를 들어, 10개의 문자를 특정 방식으로 재배열하는 경우, 고려해야 할 경우의 수는 10! = 3,628,800개이며, 일반적인 PC는 이를 1초 이내에 생성하고 테스트할 수 있다. 그러나 문자를 하나 더 추가하면, 데이터 크기가 10% 증가하지만, 경우의 수는 11배(1000%) 증가한다. 20개의 문자의 경우 경우의 수는 20!로 약 2.4×1018 또는 2.4 100경이며, 검색에 약 10년이 걸릴 것이다. 이러한 현상을 조합 폭발 또는 차원의 저주라고 한다.
체스는 조합 복잡성이 문제 해결의 어려움을 야기하는 사례이다. 체스는 해결된 게임이 아니다. 2005년에는 6개 이하의 기물로 끝나는 모든 체스 게임 엔딩이 해결되었지만, 체스 기물을 하나 더 추가하여 테이블베이스를 완성하는 데 10년이 더 걸려 7기물 테이블베이스가 완성되었다. 체스 엔딩에 기물을 하나 더 추가하는 것(8기물 테이블베이스)은 조합 복잡성의 증가로 인해 매우 어려운 문제로 여겨진다.[3][4]
3. 1. 암호학에서의 무차별 대입 공격
암호학에서 무차별 대입 공격(brute-force attack)은 올바른 키를 찾을 때까지 가능한 모든 키를 체계적으로 대입해보는 방법이다.[5] 공격자가 암호화 시스템의 약점을 이용할 수 없는 경우, 이 전략은 이론적으로 일회용 패드를 제외한 모든 암호화된 데이터에 대해 사용될 수 있다.[6]
키 길이는 무차별 대입 공격을 수행하는 실질적인 가능성을 결정하는데, 키가 길수록 짧은 키보다 기하급수적으로 해독하기 어렵다. 무차별 대입 공격은 난독화를 통해 암호화할 데이터를 난독화하여 덜 효과적으로 만들 수 있다. 이는 공격자가 코드를 해독했을 때 이를 인식하기 어렵게 만든다. 암호화 시스템의 강도를 측정하는 척도 중 하나는 공격자가 성공적인 무차별 대입 공격을 수행하는 데 이론적으로 얼마나 걸릴지를 나타낸다.
4. 탐색 속도 향상 기법
문제 종류에 특정한 휴리스틱을 사용하면 탐색 공간, 즉 후보 솔루션의 집합을 줄여서 무차별 대입 알고리즘의 속도를 높일 수 있다. 예를 들어, 8 퀸 문제에서는 퀸이 서로 공격할 수 없다는 제약 조건을 활용하여 탐색 공간을 줄일 수 있다. 모든 퀸은 서로 다른 행과 열에 배치되어야 하므로, 가능한 후보 솔루션의 수는 648에서 64!/(56!*8!) = 4,426,165,368개로 줄어든다. 이는 이전 추정치의 약 1/60,000에 해당한다.
이처럼 문제에 대한 분석을 통해 후보 솔루션의 수를 줄이면, 해결하기 어려운 문제를 비교적 쉽게 만들 수 있다. 어떤 경우에는 후보를 모든 유효한 솔루션 집합으로 줄일 수도 있다. 예를 들어, "1에서 1,000,000 사이의 정수 중에서 417로 나누어 떨어지는 모든 정수를 찾아라"라는 문제는 417부터 시작하여 417을 반복적으로 더하면서 1,000,000을 초과하는지 확인하는 방식으로 해결할 수 있다. 이 방법은 단 2398 (= 1,000,000 ÷ 417) 단계만 거치면 되며, 각 단계에서 가분성을 테스트할 필요가 없다.
4. 1. 탐색 공간 축소
문제의 특성을 이용하여 탐색해야 할 후보 해의 범위를 줄이는 방법이다. 예를 들어, 8 퀸 문제에서는 퀸의 특성을 이용하여 가능한 배치를 크게 줄일 수 있다. 각 퀸은 서로 공격할 수 없는 위치에 있어야 하므로, 같은 행이나 열, 대각선에 두 퀸이 올 수 없다. 이러한 제약 조건을 활용하면 탐색 공간을 효과적으로 줄일 수 있다.8 퀸 문제의 경우, 초기에는 64개의 칸에 8개의 퀸을 놓는 모든 경우의 수(648)를 고려해야 하지만, 퀸의 특성을 고려하면 훨씬 적은 수의 조합만으로 해를 찾을 수 있다. 두 퀸이 같은 칸에 놓일 수 없다는 점을 이용하면, 64개의 칸 중 8개를 선택하는 조합의 수(64!/(56!*8!))만큼 후보가 줄어든다. 또한, 같은 행이나 열에 두 퀸이 놓일 수 없다는 제약 조건을 추가하면, 8개의 퀸을 각 행에 하나씩 배치하고 열의 위치만 고려하는 순열의 수(8!)로 탐색 공간이 더욱 줄어든다.
이처럼 문제의 특성을 분석하고 적절한 제약 조건을 적용하면, 무차별 대입 검색의 탐색 공간을 크게 줄여 효율성을 높일 수 있다.
4. 2. 탐색 순서 최적화
해가 존재할 가능성이 높은 후보부터 먼저 탐색하는 방법이다. 예를 들어, 특정 수의 약수를 찾을 때, 작은 수부터 탐색하는 것이 더 효율적이다. ''n''이 ''c''로 나누어질 확률은 1/''c''이기 때문이다.후보가 유효할 확률은 이전 실패 이력에 영향을 받는 경우가 많다. 예를 들어, 1000비트 문자열 ''P''에서 '''1''' 비트를 찾는 문제를 보자. 후보는 1에서 1000까지의 인덱스이며, ''P''[''c''] = '''1'''이면 후보 ''c''는 유효하다. ''P''의 첫 비트가 '''0''' 또는 '''1'''일 확률이 같고, 이후 각 비트는 90% 확률로 이전 비트와 같다고 가정하자. 후보를 1부터 1000까지 순차적으로 증가시키면, 성공 전 검사되는 후보 수 ''t''의 평균은 약 6이다. 반면, 후보를 1, 11, 21, 31...991, 2, 12, 22, 32 등 순서로 열거하면, ''t''의 기댓값은 2보다 약간 더 크다.
일반적으로 검색 공간은 이전 시도가 실패했다는 점을 고려하여 다음 후보가 유효할 가능성이 가장 높도록 열거해야 한다. 유효한 솔루션이 "클러스터화"될 가능성이 높다면, 각 새 후보는 이전 후보와 최대한 멀리 떨어져 있어야 한다. 반대로, 솔루션이 예상보다 균일하게 퍼져 있을 가능성이 있다면 마찬가지이다.
4. 3. 휴리스틱 활용
문제에 대한 사전 지식(휴리스틱)을 활용하여 탐색 공간을 줄이거나 탐색 순서를 최적화할 수 있다. 예를 들어, 8 퀸 문제에서는 퀸들이 서로 공격할 수 없다는 제약 조건을 이용하여 탐색 공간을 크게 줄일 수 있다.[1]게임 트리 탐색에서 사용되는 미니맥스 알고리즘은 휴리스틱 활용의 좋은 예시이다. 미니맥스 알고리즘은 탐색 초기 단계에서 많은 하위 트리를 제거하여 탐색 효율성을 높인다.[1] 컴퓨터 체스에서도 이와 비슷한 방식으로 탐색 트리를 가지치기하고, 나머지 트리를 정적 평가 함수로 근사하여 탐색 공간을 줄인다.[1]
구문 분석 분야의 차트 파서와 같은 기술도 문제의 제약 조건을 활용하여 복잡성을 줄이는 데 사용된다.[1]
5. 다른 탐색 알고리즘과의 비교
휴리스틱은 탐색의 일부를 조기에 차단하는 데 사용될 수 있다. 미니맥스법은 게임 트리 탐색에서 탐색 초기 단계에 많은 하위 트리를 제거하는 예시이다.[1] 차트 파싱과 같은 기법은 구문 분석 등의 분야에서 문제의 제약 조건을 활용하여 지수 함수적 복잡성의 문제를 다항식 수준의 복잡성을 가진 문제로 줄인다.[1]
컴퓨터 체스와 같이 문제를 단순화하여 탐색 공간을 줄일 수도 있다. 컴퓨터 체스에서는 특정 수순에서 트리를 가지치기하고, 나머지 트리를 평가 함수로 근사하여, 완전한 미니맥스법 탐색 트리보다 제한된 탐색 트리를 구할 수 있다.
5. 1. 제약 조건 만족 문제 해결 알고리즘
휴리스틱은 검색의 일부를 조기에 차단하는 데 사용될 수 있다. 이러한 예 중 하나는 검색 초기 단계에서 많은 하위 트리를 제거하는 게임 트리를 검색하기 위한 미니맥스 원리이다.[1] 언어 구문 분석과 같은 특정 분야에서는 차트 파싱과 같은 기술을 사용하여 문제의 제약 조건을 활용하여 지수 복잡성 문제를 다항식 복잡성 문제로 줄일 수 있다.[1] 제약 만족 문제와 같은 많은 경우에 제약 전파를 통해 검색 공간을 극적으로 줄일 수 있으며, 이는 제약 프로그래밍 언어에서 효율적으로 구현된다.[1]5. 2. 분기 한정법 (Branch and Bound)
휴리스틱은 탐색 과정에서 일부 하위 트리를 제거하는 데 사용될 수 있다. 분기 한정법은 이러한 기법 중 하나로, 탐색 초기 단계에서 유망하지 않은 분기를 제거하여 탐색 효율성을 높인다. 예를 들어, 컴퓨터 체스에서는 게임의 모든 가능한 수를 계산하는 대신, 특정 수에서 탐색을 중단하고 정적 평가 함수를 사용하여 나머지 부분을 근사하는 방식으로 탐색 효율성을 높일 수 있다.5. 3. 유전 알고리즘 (Genetic Algorithm)
유전 알고리즘(Genetic Algorithm영어)은 자연 선택과 유전의 원리를 모방하여 최적해를 찾는 알고리즘이다. 주어진 소스에는 유전 알고리즘에 대한 직접적인 설명은 없지만, "해결책에 대해 가지고 있을 수 있는 다양한 종류의 부분적인 지식을 활용하도록 설계된 다른 많은 검색 방법 또는 메타휴리스틱이 있습니다"라는 문장을 통해 유전 알고리즘이 메타휴리스틱 검색 방법의 일종임을 추론할 수 있다.참조
[1]
웹사이트
Brute Force Algorithms Explained
https://www.freecode[...]
2020-01-06
[2]
웹사이트
Complexity of brute force search
https://www.coursera[...]
2018-06-14
[3]
웹사이트
Is there a freely available online 7 piece Endgame tablebase?
https://chess.stacke[...]
[4]
웹사이트
Lomonosov Endgame Tablebases
http://chessok.com/?[...]
[5]
Webarchive
Blocking Brute Force Attacks
http://www.cs.virgin[...]
2016-12-03
[6]
서적
Understanding Cryptography: A Textbook for Students and Practitioners
http://www.crypto-te[...]
Springer
[7]
웹인용
Brute Force Algorithms Explained
https://www.freecode[...]
2020-01-06
[8]
웹인용
Complexity of brute force search
https://www.coursera[...]
2018-06-14
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com